import java.io.BufferedInputStream;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.util.HashMap;


public class optimizer {

	HashMap selectivity;
	int r, t, l, m,	a, f;

	public optimizer(){
		selectivity = new HashMap();
		getConfig();
		findOpt();
	}

	//read in the config.txt file
	public void getConfig(){
		String str = "";
		try {
			File file = new File("query_folder\\config.txt");
			//System.out.println(file.getAbsolutePath());
			FileInputStream fis = new FileInputStream(file);
			BufferedInputStream bis = new BufferedInputStream(fis);
			DataInputStream dis = new DataInputStream(bis);
			while(dis.available() != 0){
				String[] temp = dis.readLine().split("\\s+=\\s+");
				if (temp[0].equals("r"))
					this.r = Integer.parseInt(temp[1]);
				else if (temp[0].equals("t"))
					this.t = Integer.parseInt(temp[1]);
				else if (temp[0].equals("l"))
					this.l = Integer.parseInt(temp[1]);
				else if (temp[0].equals("m"))
					this.m = Integer.parseInt(temp[1]);
				else if (temp[0].equals("a"))
					this.a = Integer.parseInt(temp[1]);
				else if (temp[0].equals("f"))
					this.f = Integer.parseInt(temp[1]);
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}


	//return false if there is not intersect, otherwise return true.
	public boolean checkAnd(String str1, String str2){
		int length = str1.length();
		for (int i = 0; i < length; ++i){
			if (str1.charAt(i) == '1' && str2.charAt(i) == '1'){
				return true;
			}
		}
		return false;
	}

	public void findOpt(){
		String str = "";
		try {
			File file = new File("query_folder\\query.txt");
			//System.out.println(file.getAbsolutePath());
			FileInputStream fis = new FileInputStream(file);
			BufferedInputStream bis = new BufferedInputStream(fis);
			DataInputStream dis = new DataInputStream(bis);
			while(dis.available() != 0){
				str = str + dis.readLine() + "\n";
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
		String[] queries = str.split("\n");
		int length = queries.length;
		for (int i = 0; i < length; ++i){
			String[] query = queries[i].split("\\s+");
			int templ = query.length;
			double[] terms;
			terms = new double[templ];
			for (int j = 0; j < templ; ++j){
				terms[j] = Double.parseDouble(query[j]);
			}
			selectivity.put(i, terms);
		}

		for (int i = 0; i < length; ++i){
			// process each query
			System.out.println("start a new query");
			double[] select = (double[]) selectivity.get(i);
			int l = select.length;
			int last = (int) Math.pow(2, l);

			// initialize the table used for dynamic programming
			int[] L = new int[last-1];
			int[] R = new int[last-1];
			double[] c = new double[last-1];
			int[] b = new int[last-1];
			double[] combp = new double[last-1];
			double[] fcost = new double[last-1];

			for (int j = 1; j < last; ++j){

				L[j-1] = -1;
				R[j-1] = -1;
				String temp = Integer.toBinaryString(j);
				while (temp.length()<l){
					temp = "0"+temp;
				}// insert 0 at the beginning.

				int k = this.getK(temp);
				double nbcost = k * this.r + (k - 1) * this.l + k * this.f + this.a;
				double q = 0;
				double p = this.getMultiP(temp, i);
				if (p <= 0.5)
					q = p;
				else
					q = 1 - p;
				double lacost = k * this.r + (k - 1) * this.l + k * this.f + this.t + this.m * q + p * this.a;
				combp[j-1] = p;
				fcost[j-1] = k * this.r + (k - 1) * this.l + k * this.f + this.t;
				if(nbcost < lacost){
					c[j-1] = nbcost;
					b[j-1] = 1;
				}else{
					c[j-1] = lacost;
					b[j-1] = 0;
				}
			}

			for (int j = 1; j < last; ++j){// each subset s
				String str_s = Integer.toBinaryString(j);
				while (str_s.length()<l){
					str_s = "0"+str_s;
				}// insert 0 at the beginning.
				// System.out.println(str_s);
				for (int k = 1; k < last; ++k){// each subset s'
					String str_s_prime = Integer.toBinaryString(k);
					while (str_s_prime.length()<l){
						str_s_prime = "0"+str_s_prime;
					}// insert 0 at the beginning.

					if (!checkAnd(str_s, str_s_prime)){// there is not intersect between these two subset

						//check lemma 4.8
						double c_metric_s_prime =(combp[k-1]-1)/fcost[k-1];
						double p1 = combp[k-1];
						//find the left most &-term in s
						int left = j;
						left --;
						if(L[left] != -1){
							left = L[left];
						}
						double leftmost_c_metric_s = (combp[left]-1)/fcost[left];
						double p2 = combp[left];
						if(c_metric_s_prime > leftmost_c_metric_s && p1 > p2){
							//do nothing
						}else{
							//check lemma 4.9
							double d_metric_s_prime = fcost[k-1];
							int iter = j;
							boolean flag = false;
							iter --;
							while(L[iter] != -1){
								left = L[iter];
								double d_metric_s_some = fcost[left];
								p2 = combp[left];
								if (p1 <= 0.5 && d_metric_s_prime > d_metric_s_some && p1 > p2){
									//do nothing
									flag = true;
									break;
								}else{
									// find some other &terms
									iter = R[iter];
								}
							}
							// it is the right most &term
							if(!flag){
								double d_metric_s_some = fcost[iter];
								p2 = combp[iter];
								if (p1 <= 0.5 && d_metric_s_prime > d_metric_s_some && p1 > p2){
									flag = true;
								}
							}
							if(!flag){// calculate the cost of s'&& s
								double p = combp[k-1] ;
								double q = Math.min(p, 1-p);
								double newC = fcost[k-1] + this.m * q + p * c[j-1];
								int combination = j+k;
								if (newC < c[combination-1]){
									if (i == 2){
										//System.out.println(k+" "+j);
									}
									c[combination-1] = newC;
									L[combination-1] = k-1;
									R[combination-1] = j-1;
								}
							}
						}

					}
				}
			}
			String str_s = Integer.toBinaryString(last-1);
			String str_l = Integer.toBinaryString(L[last-2]+1);
			String str_r = Integer.toBinaryString(R[last-2]+1);
			System.out.println(str_s + " c=" +c[last-2]+ " L=" +str_l+ " R=" +str_r+" b=" + b[last-2]);
			if(i == 2){
				for(int m = 1; m < last; ++m ){
					str_s = Integer.toBinaryString(m);
					while (str_s.length()<l){
						str_s = "0"+str_s;
					}// insert 0 at the beginning.
					str_l = Integer.toBinaryString(L[m-1]+1);
					str_r = Integer.toBinaryString(R[m-1]+1);
					//System.out.println(str_s + " c=" +c[m-1]+ " L=" +str_l+ " R=" +str_r+" b=" + b[m-1] + " fcost=" + fcost[m-1]+ " p="+combp[m-1]);
				}
			}
			
			/*
			 *  output, plz change this part of code
			 */
			String query = "";
			int iter = last-1;
			if (L[iter-1] == -1){
				query = "\tanswer[j] = i;\n\tj += ";
				query = outputLogicAnd(Integer.toBinaryString(iter));
				System.out.println(query);
			}else{
				iter --;
				while(R[iter] != -1){
					int left = L[iter];
					left ++;
					str_l = Integer.toBinaryString(left);
					while (str_l.length()<l){
						str_l = "0"+str_l;
					}
					if (query != "")
						query = query + "(" + outputLogicAnd(str_l) +"&&";
					else
						query = outputLogicAnd(str_l);
					iter = R[iter];
				}
				System.out.println(query);
			}
			/*
			 * output end 
			 */
			
		}

	}

	public String outputLogicAnd(String str){
		String answer = "(";
		for (int i = 0; i < str.length(); ++i){
			if(str.charAt(i)=='1'){
				String count = Integer.toString(i+1);
				answer = answer + "t"+count+"[o"+count+"[i]] & ";
			}
		}
		answer = answer.substring(0, answer.length()-3);
		answer = answer + ")";
		return answer;
	}

	public int getK(String str){
		int count = 0;
		for (int i = 0; i < str.length(); ++i){
			if (str.charAt(i) == '1'){
				count ++;

			}
		}
		return count;
	}

	public double getMultiP(String str, int index){
		double p = 1;
		double[] select = (double[]) selectivity.get(index);

		for (int i = 0; i < str.length(); ++i){
			if (str.charAt(i) == '1'){
				p = p * select[i];
			}
		}

		return p;
	}


}